package 中等.动态规划.其他;

/**
 * 有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：
 * <p>
 * 提供 100ml 的 汤A 和 0ml 的 汤B 。
 * 提供 75ml 的 汤A 和 25ml 的 汤B 。
 * 提供 50ml 的 汤A 和 50ml 的 汤B 。
 * 提供 25ml 的 汤A 和 75ml 的 汤B 。
 * 当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同
 * 为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，
 * 我们将尽可能分配。当两种类型的汤都分配完时，停止操作。
 * 注意 不存在先分配 100 ml 汤B 的操作。
 * 需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。
 * 返回值在正确答案 10-5 的范围内将被认为是正确的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/soup-servings
 */
public class 分汤_808 {

    public static void main(String[] args) {

        System.out.println(soupServings(20000));

    }

    /**
     * 子问题：
     * dp[i][j] 表示 A 汤剩余 i 毫升，B 汤剩余 j 毫升，返回的概率
     * 分配操作都是 25 的倍数
     * 4 0
     * 3 1
     * 2 2
     * 1 3
     * n 也要 /25 并且向上取值
     * 状态转移方程：
     * dp[i][j]=0.25*(dp[i-4][j]+dp[i-3][j-1]+dp[i-2][j-2]+dp[i-1][j-3])
     * 初始化值：
     * 注意：如果汤的剩余量不足以完成某次操作，我们将尽可能分配的意思是必须在四种
     * 情况里面选择一种合适的，否则停止分配
     * 当 i = 0，j = 0 时，汤A 先分配完的概率为 0，汤A和汤B 同时分配完的概率为 1
     * 此时 dp[0][0] = 0 + 1/2 =0.5
     * 当 i = 0，j > 0 时，汤A 先分配完的概率为 1，汤A和汤B 同时分配完的概率为 0
     * 此时 dp[0][j] = 1
     * 当 i > 0，j = 0 时，汤A 先分配完的概率为 0，汤A和汤B 同时分配完的概率为 0
     * 此时 dp[i][0] = 0
     */
    public static double soupServings(int n) {
        n = n % 25 == 0 ? n / 25 : n / 25 + 1;
        // 每次分配操作有 (4, 0),(3, 1),(2, 2),(1, 3)(4,0),(3,1),(2,2),(1,3) 四种，
        // 那么在一次分配中，汤 AA 平均会被分配的份数期望为
        // E(A) = (4 + 3 + 2 + 1)\times 0.25 = 2.5E(A)=(4+3+2+1)×0.25=2.5 ，
        // 汤 BB 平均会被分配的份数期望为
        // E(B) = (0 + 1 + 2 + 3) \times 0.25 = 1.5E(B)=(0+1+2+3)×0.25=1.5。
        // 因此在 nn 非常大的时候，汤 AA 会有很大的概率比 BB 先分配完，汤 AA 被先
        // 取完的概率应该非常接近 1
        if (n >= 179) {
            return 1.0;
        }

        double[][] dp = new double[n + 1][n + 1];
        for (int j = 0; j < n + 1; j++) {
            dp[0][j] = 1;
        }
        dp[0][0] = 0.5;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = 0.25 * (dp[Math.max(0, i - 4)][j] +
                        dp[Math.max(0, i - 3)][Math.max(0, j - 1)] +
                        dp[Math.max(0, i - 2)][Math.max(0, j - 2)] +
                        dp[Math.max(0, i - 1)][Math.max(0, j - 3)]);
            }
        }

        return dp[n][n];
    }

}
